package com.lc.hot100.lc45;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		
	}
}

class Solution1 {
    public int jump(int[] nums) {
        int n = nums.length;
    	int[] f = new int[n];
    	
    	Arrays.fill(f, Integer.MAX_VALUE);
    	f[0] = 0;
    	for (int i = 0; i < n - 1; i ++) {
    		int step = nums[i];
    		for (int j = 1; j <= step && i + j <= n - 1; j ++) {
    			f[j + i] = Math.min(f[j + i], f[i] + 1);
    		}
    	}
    	return f[n - 1];
    	
    }
}

class Solution {
    public int jump(int[] nums) {
        int maxPosition = 0;
        int end = 0;
        int step = 0;
        for (int i = 0; i < nums.length - 1; i ++) {
        	maxPosition = Math.max(maxPosition, i + nums[i]);
        	if (i == end) {
        		end = maxPosition;
        		step ++;
        	}
        }
        return step;
    }
}
